package com.sise.Backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 *      491. 递增子序列
 *
 *      给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
 *      数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
 *
 *      输入：nums = [4,6,7,7]
 *      输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
 *      示例 2：
 *
 *      输入：nums = [4,4,3,2,1]
 *      输出：[[4,4]]
 */
public class _491_findSubsequences {

    public static List<List<Integer>> findSubsequences(int[] nums) {
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        backtracking(nums, 0, path, res);
        return res;
    }

    private static void backtracking(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        // 因为题目要求是返回至少两个元素，并且是递增子序列，所以条件是加入 path 路径的长度大于1即可
        // 但是这里注意的是不能 return，因为 return 了只能返回 path.size==nums.length 的最后一个集合
        if (path.size() > 1) {
            res.add(new ArrayList<>(path));
        }
        // 这里十分注意，对于 used 数组如果写在函数里面，代表会对同一树层上和同一树枝上的重复元素都不能重复使用。
        // 而写成下面这样，是只对同一树层上的重复元素不能重复使用
        // 造成这种结果的原因是因为写在函数里面的 used 数组不会因为像下递归的时候去更新used数组，一直使用的传入的used这个参数。
        /**
         这里简单举个例子吧，没图的话本来也不大好理解，nums={4,7,6,7},当走到第二层调用到 7 时，此时如果 used 写在函数里面的话，
         是不是已经使用一次了对吧，像下再执行到 7 时，就不再使用了。此时回溯到 6 时，也是在第二层，当执行过后，然后像下再执行时 7时，
         也不再使用了。说白了原因就是因为没更新 used 数组。
         为什么我举例跟样例不一样呢？是因为他的样例比较误导咱们做题，画图时会很不容易得到他的结果集，你们可以根据我举的例子
         和解释去画下图吧。

         在 path 中含有元素的情况下，
         如果当前遍历到的 nums[i] 比 path 中最后添加的那个元素要小的话，
         那么就构不成递增序列，此时直接 continue。

         由于题意是 -100 <= nums[i] <= 100，所以下面的代码 used[nums[i] + 100] = 1 防止重复
         */

        // 在 for 循环外面定义 used[]，代表的是本层循环(有 nums.length 个树分支)，而不是 dfs 递归往下循环
        int[] used = new int[201];
        for (int i = start; i < nums.length; i++) {
            // used[nums[i] + 100 题目要求
            if (path.size() != 0 && nums[i] < path.get(path.size() - 1) || (used[nums[i] + 100] == 1)) continue;
            used[nums[i] + 100] = 1;// 记录这个元素在本层用过了，本层后面不能再用了
            path.add(nums[i]);
            backtracking(nums, i + 1, path, res);
            //这里used数组不赋值为0，是因为不再回溯，为什么不回溯，还是老规矩看我的那几道题讲解吧
            path.remove(path.size() - 1);
        }
    }
}
